/*
 * Copyright (C), 2015-2018
 * FileName: Solution047
 * Author:   zhao
 * Date:     2018/12/5 18:27
 * Description: 47. 全排列 II
 * History:
 * <author>          <time>          <version>          <desc>
 * 作者姓名           修改时间           版本号              描述
 */
package com.lizhaoblog.mid;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.Collections;
import java.util.List;

/**
 * 〈一句话功能简述〉<br>
 * 〈47. 全排列 II〉
 *
 * @author zhao
 * @date 2018/12/5 18:27
 * @since 1.0.1
 */
public class Solution047 {
    /**************************************
     * 题目

     给定一个可包含重复数字的序列，返回所有不重复的全排列。

     示例:

     输入: [1,1,2]
     输出:
     [
     [1,1,2],
     [1,2,1],
     [2,1,1]
     ]
     **************************************/

    /*************************************
     想法：
     利用046的方法，多加一个boolean[] visit = new boolean[nums.length];，将已经加入进去的数据设为true
     还有个核心就是Arrays.sort(nums); 对数组进行排序

     我的做法

     超过43%的测试案例

     时间复杂度/空间复杂度：  /

     代码执行过程：
     result: []smallResult: []
     result: []smallResult: [1]
     result: []smallResult: [1, 1]
     result: []smallResult: [1, 1, 2]
     result: [[1, 1, 2]]smallResult: [1, 2]
     result: [[1, 1, 2]]smallResult: [1, 2, 1]
     result: [[1, 1, 2], [1, 2, 1]]smallResult: [2]
     result: [[1, 1, 2], [1, 2, 1]]smallResult: [2, 1]
     result: [[1, 1, 2], [1, 2, 1]]smallResult: [2, 1, 1]
     总结：

     ************************************/
    public List<List<Integer>> permuteUnique(int[] nums) {
        if (nums.length == 0) {
            return Collections.EMPTY_LIST;
        }
        Arrays.sort(nums);
        boolean[] visit = new boolean[nums.length];
        List<List<Integer>> result = new ArrayList<>();
        List<Integer> smallResult = new ArrayList<>();
        repick(nums, result, smallResult, visit);
        return result;
    }

    private void repick(int[] nums, List<List<Integer>> result, List<Integer> smallResult, boolean[] visit) {
        System.out.println("result: " + result.toString() + "smallResult: " + smallResult.toString());
        if (smallResult.size() == nums.length) {
            //            result.add(new ArrayList<Integer>(smallResult));
            result.add(smallResult);

        } else {
            for (int i = 0; i < nums.length; i++) {
                if (visit[i] || (i > 0 && nums[i] == nums[i - 1] && !visit[i - 1])) {
                    continue;
                }
                visit[i] = true;
                List<Integer> tmp = new ArrayList<>(smallResult);
                //                smallResult.add(nums[i]);
                tmp.add(nums[i]);
                repick(nums, result, tmp, visit);
                //                smallResult.remove(smallResult.size() - 1);
                visit[i] = false;
            }

        }
    }

    /**************************************
     * 比我好的答案 better
     * ***********************************/
    List<List<Integer>> result = new ArrayList<>();

    public List<List<Integer>> better(int[] nums) {
        if (nums.length == 0) {
            return result;
        }
        Arrays.sort(nums);
        func(new ArrayList<Integer>(), nums, new boolean[nums.length]);
        return result;
    }

    private void func(List<Integer> candidates, int[] nums, boolean[] used) {
        if (candidates.size() == nums.length) {
            result.add(new ArrayList<>(candidates));
        }
        //不能直接add(candidates)
        else {
            for (int i = 0; i < nums.length; ++i) {
                if (used[i] || (i != 0 && nums[i] == nums[i - 1] && !used[i - 1])) {
                    continue;
                }
                used[i] = true;
                candidates.add(nums[i]);
                func(candidates, nums, used);
                used[i] = false;
                candidates.remove(candidates.size() - 1);
            }
        }
    }
}
